#include "Tarjan.h"
#include <algorithm>
#include <set>
#include <map>
#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream F;
    F.open("input.txt");

    vector<pair<int, int>> edges;
    int numberOfEdges = 0;
    int numberOfVertexes = 0;
    int from = 0, to = 0;
    set<int> existingVertexes;
    map<int, int> inputVertexCompliance;
    map<int, int> outputVertexCompliance;

    while (!F.eof())
    {
        F >> from >> to;
        edges.push_back(make_pair(from, to));
        existingVertexes.insert(edges[numberOfEdges].first);
        existingVertexes.insert(edges[numberOfEdges++].second);
    }

    numberOfVertexes = existingVertexes.size();
    CGraph<int, int> graph(0, 0, numberOfVertexes);

    int i = 0;
    for (auto it = existingVertexes.begin(); it != existingVertexes.end(); ++it, ++i)
    {
        inputVertexCompliance[*it] = i;
        outputVertexCompliance[i] = *it;
        graph.addVertexWeight(i, 1);
    }

    for (auto it = edges.begin(); it != edges.end(); ++it)
    {
        graph.addEdge(inputVertexCompliance[(*it).first], inputVertexCompliance[(*it).second], 1);
    }

    SCCTarjan<CGraph<int, int>> scc;
    vector<vector<int>> comps = scc.Process(&graph);

    for (auto it = comps.rbegin(); it != comps.rend(); ++it)
    {
        sort((*it).begin(), (*it).end());
        for (auto i:(*it))
        {
            cout << outputVertexCompliance[i] << " ";
        }
        cout << endl;
    }

    return 0;
}
